Extragradient method with variance reduction for stochastic variational inequalities

摘要

We propose an extragradient method with stepsizes bounded away from zero forstochastic variational inequalities requiring only pseudo-monotonicity. Weprovide convergence and complexity analysis, allowing for an unbounded feasibleset, unbounded operator, non-uniform variance of the oracle and, also, we donot require any regularization. Alongside the stochastic approximationprocedure, we iteratively reduce the variance of the stochastic error. Ourmethod attains the optimal oracle complexity $\mathcal{O}(1/\epsilon^2)$ (up toa logarithmic term) and a faster rate $\mathcal{O}(1/K)$ in terms of the mean(quadratic) natural residual and the D-gap function, where $K$ is the number ofiterations required for a given tolerance $\epsilon>0$. Such convergence raterepresents an acceleration with respect to the stochastic error. The generatedsequence also enjoys a new feature: the sequence is bounded in $L^p$ if thestochastic error has finite $p$-moment. Explicit estimates for the convergencerate, the oracle complexity and the $p$-moments are given depending on problemparameters and distance of the initial iterate to the solution set. Moreover,sharper constants are possible if the variance is uniform over the solution setor the feasible set. Our results provide new classes of stochastic variationalinequalities for which a convergence rate of $\mathcal{O}(1/K)$ holds in termsof the mean-squared distance to the solution set. Our analysis includes thedistributed solution of pseudo-monotone Cartesian variational inequalitiesunder partial coordination of parameters between users of a network.